/*
2022-2-27 
https://leetcode-cn.com/problems/minimum-time-to-finish-the-race/
*/
#define LL long long
class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        const int n=tires.size();
        vector<LL> mintime(21,INT_MAX);
        for(int i=0;i<n;i++)
        {
            LL r=0;
			for(int j=1;j<=20;j++)
            {
                r=r*tires[i][1]+tires[i][0];
                if(r>INT_MAX) 
                    break;
                mintime[j]=min(r,mintime[j]);
            }
        }
        vector<LL> f(numLaps+1,INT_MAX);
        f[0]=-changeTime;
        for(int i=1;i<=numLaps;i++)
            for(int j=1;j<=min(20,i);j++)
                f[i]=min(f[i],f[i-j]+changeTime+mintime[j]);
        
        return f[numLaps];
    }
};
